package arithmetic.detectcycle;

import java.util.HashMap;
import java.util.Map;

/**
 * 环形列表2：给定一个链表，返回链表开始入环的第一个节点。如果列表无环，则返回null
 *
 * 进阶：你是否可以使用 O(1) 空间解决此题？
 */
public class Test {

    public static void main(String[] args) {

    }

    public static ListNode detectCycle(ListNode head){
        if (head==null) return null;
        ListNode slow = head;
        ListNode fast = head;
        boolean exist=false;
        while (fast.next !=null && fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow == fast){
                exist=true;
                break;
            }
        }
        //存在环形--将slow指针还原重新开始
        if(exist){
            slow=head;
            while (slow != fast){
                slow=slow.next;
                fast=fast.next;
            }
            return slow;
        }
        return null;
    }

    public static ListNode detectCycle1(ListNode head){
        if (head == null ) return null;
        Map map = new HashMap<ListNode, ListNode>();
        while (head != null){
            if(map.get(head) != null){
                return  (ListNode) map.get(head);
            }
            map.put(head,head);
            head=head.next;
        }
        return null;
    }

}


class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val=x;
        next=null;
    }
}